package Tree_09.BinarySortTree_07;

/*
 * @Author 罗
 * @date 2020/3/26 - 2:59 上午
 *
 */

public class BinarySortTree {
    private NodeForBinarySortTree root;

    /**
     * 根据节点id删除节点
     *
     * @param id
     */
    public void deleteById(int id) {
        if (root == null) {
            return;
        }
        /*
         * 1.找到要删除节点的前一个节点
         * */
        NodeForBinarySortTree parentNode = findTheNodeBeforeTargetNode(id, root);
        if (parentNode == null) {
            /*
             * 如果要删除的节点是根节点，则无法获取根节点的父节点
             * 判断要删除的节点是不是根节点
             * */
            if (id == root.value) {
                /*
                 * 删除根节点
                 * */
                deleteRootNode();
            }

            System.out.println("节点未找到");
            return;
        }

        NodeForBinarySortTree singleGrandSon = null;
        if (parentNode.left != null && parentNode.left.value == id) {
            /*
             * targetNode是parentNode的左子节点
             * 获取parentNode的左边孙节点
             * */
            singleGrandSon = getGrandSonNode(parentNode.left);
            /*
             * 将父节点的left指向孙节点
             * */
            parentNode.left = singleGrandSon;
        } else if (parentNode.right != null) {
            /*
             * targetNode是parentNode的右子节点
             * 获取parentNode的右边孙节点
             * */
            singleGrandSon = getGrandSonNode(parentNode.right);
            /*
             * 将父节点的right指向孙节点
             * */
            parentNode.right = singleGrandSon;
        }


    }

    /**
     * 删除根节点
     */
    private void deleteRootNode() {


        if (root.left != null && root.right != null) {
            /*
             * 根节点有左右子树的情况
             * */
            add(root.left, root.right);
            root = root.right;
        } else {
            if (root.left != null) {
                root = root.left;
            } else if (root.right != null) {
                root = root.right;
            } else {
                /*
                 * 根节点不含左右节点
                 * */
                root = null;
            }
        }
        return;

    }

    /**
     * 获取被删除节点的单个子节点，即父节点的孙节点
     * 如果被删除的节点含有左右两个节点，则将左子树挂在到右子树上
     *
     * @param deletedNode
     * @return
     */
    private NodeForBinarySortTree getGrandSonNode(NodeForBinarySortTree deletedNode) {
        if (deletedNode.left == null && deletedNode.right != null) {
            /*
             * targetNode只有右子节点
             * 将右子节点返回
             * */
            return deletedNode.right;
        }
        if (deletedNode.left != null && deletedNode.right == null) {
            /*
             * targetNode只有左子节点
             * 将左子节点返回
             */
            return deletedNode.left;
        }
        if (deletedNode.left == null && deletedNode.right == null) {
            return null;
        } else {
            /*
             * 要删除的节点的含有两棵（左右）子树
             * 将左子树挂在到右子树上
             * */
            add(deletedNode.left, deletedNode.right);
            /*
             *  将右子树返回
             * */
            return deletedNode.right;
            /*
             * 另外一种思路是找到被删除节点右子树的最小节点（右子树一直向left查找，右子树的最左叶子节点）
             *  并把最小节点删除，将最小节点的value返回，然后将最小节点的value赋值给被删除节点
             *  这样覆盖后的被删除节点的右边就是原来被删除节点的右子树
             *  而且右子树的任意值都比覆盖后的最小节点大
             *  而被删除节点的左子树保持不变，因为被删除节点的右子树的最小值都要比被删除节点的左子树的最大值大
             *
             * */
        }
    }

    /**
     * 找到要删除节点的前一个节点
     *
     * @param targetNodeId
     * @param parent
     * @return
     */
    private NodeForBinarySortTree findTheNodeBeforeTargetNode(int targetNodeId, NodeForBinarySortTree parent) {
        /*
         * 要找的节点的值比当前节点的值小，准备向左递归
         * */
        if (parent.left != null && targetNodeId < parent.value) {
            /*
             * 要查找的节点id与当前节点的左节点id相同，返回当前节点
             * */
            if (targetNodeId == parent.left.value) {
                return parent;
            }
            /*
             * 继续向左递归
             * */
            return findTheNodeBeforeTargetNode(targetNodeId, parent.left);

        }

        if (parent.right != null && targetNodeId >= parent.value) {
            if (targetNodeId == parent.right.value) {
                return parent;
            }
            return findTheNodeBeforeTargetNode(targetNodeId, parent.right);

        }

        return null;
    }

    /**
     * 将添加方法移动到BinarySortTree中，node节点不需要多余的方法
     *
     * @param node
     */
    public void add2(NodeForBinarySortTree node) {
        if (root == null) {
            root = node;
            return;
        }
        if (node == null) {
            System.out.println("请不要添加null节点");
            return;
        }

        add(node, root);
    }

    /**
     * 将添加方法从节点中分离出来，实现解偶
     *
     * @param node 新添加的节点
     * @param temp 节点将被添加到的子树
     */
    private void add(NodeForBinarySortTree node, NodeForBinarySortTree temp) {

        if (node.value < temp.value) {
            if (temp.left == null) {
                temp.left = node;
            } else {
                add(node, temp.left);
            }
        } else {
            if (temp.right == null) {
                temp.right = node;
            } else {
                add(node, temp.right);
            }
        }

    }

    /**
     * 重载add(NodeForBinarySortTree node)，使其可以直接添加int数据
     *
     * @param value
     */
    public void add(int value) {
        this.add(new NodeForBinarySortTree(value));
    }

    /**
     * 添加节点
     *
     * @param node
     */
    public void add(NodeForBinarySortTree node) {
        if (root == null) {
            root = node;
            return;
        }
        root.add(node);
    }

    /**
     * 中序遍历
     * 二叉排序树，用中序遍历就是有序的
     */
    public void infixList() {
        NodeForBinarySortTree.infixList(this.root, 0);
    }

    public void setRoot(NodeForBinarySortTree root) {
        this.root = root;
    }

    public NodeForBinarySortTree getRoot() {
        return root;
    }
}
